package 机器人的运动范围;
//题目描述
//地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
// 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
// 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
// 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
// 请问该机器人能够达到多少个格子？
public class Solution
{
    int count=0;
    //跟矩阵中的路径一样的回溯算法，每次只考虑这一步应该怎么做
    public int movingCount(int threshold, int rows, int cols)
    {
       boolean[] pass=new boolean[rows*cols];

        movingCount(threshold,0,0,rows,cols,pass);
        return count;
    }
    public void movingCount(int threshold,int i,int j, int rows, int cols,boolean[] pass)
    {
        int index=i*cols+j;
        //终止条件
        if (i<0||j<0||i>=rows||j>=cols||pass[index]==true)
            return;
        //判断行列加和是否小于规定的数
        if (helper(i,j)<=threshold)
        {
            count++;
            pass[index]=true;
        }
        else
        {
            pass[index]=false;
            return;
        }
        //向四周试探
        movingCount(threshold, i-1, j, rows, cols, pass);
        movingCount(threshold, i+1, j, rows, cols, pass);
        movingCount(threshold, i, j-1, rows, cols, pass);
        movingCount(threshold, i, j+1, rows, cols, pass);



    }
    public int helper(int i,int j)
    {
        int res=0;
        while (i/10>0)
        {
            res=res+i%10;
            i=i/10;
        }
        res+=i;
        while (j/10>0)
        {
            res=res+j%10;
            j=j/10;
        }
        res+=j;
        return res;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.helper(123,123));
    }
}
